package leetcode_core.leetcode_5;

import java.util.Arrays;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年11月22日 14:38
 */
public class MinPathSum {
    private int[][] memo;
    //表示从(0,0)走到(i,j)所需要的最短距离
    private int dp(int i,int j,int[][] grid){
        if(i == 0 && j==0){
            return grid[0][0];//base-case
        }
        //如果索引出界,那么就会返回一个很大的值
        if(i < 0 || j<0){
            return Integer.MAX_VALUE;
        }
        //状态转移,从加上这个格子和其他路径的和
        if(memo[i][j] == -1){
            memo[i][j] = Math.min(dp(i-1,j,grid),dp(i,j-1,grid))+grid[i][j];
        }
        return memo[i][j];
    }

    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        memo = new int[n][m];
        Arrays.fill(memo,-1);
        int sum = dp(n-1,m-1,grid);
        return sum;
    }
}
